1. Field of the Invention
The present invention relates to a strict recognizing apparatus for recognizing, for example, the center of gravity of an object existing in the environment for use in a document structure interpreting process, in operating an object through a manipulator, and in the navigation of a movable robot, etc.
The present invention also relates to a strict recognizing apparatus for storing the shape information about objects and graphics as object models, and estimating a parameter describing the environment, for example, an object existing in the environment, type of graphics and position-and-postures, etc. based on the characteristic points obtained by observing the environment.
2. Description of the Related Art
Recently, the appliances provided with the above-described recognizing apparatus have been widely used, and the environment in which these appliances are operated has been improved not only in fixed areas but also the areas that are under development and have uncertain conditions. Therefore, a strict recognizing apparatus capable of correctly recognizing an object even in an uncertain environment is earnestly expected to play an important part as a component of the appliances.
A typical example of a strict recognizing apparatus capable of correctly recognizing an object especially in an environment full of different types of noise is a strict recognizing apparatus based on a generalized Hough transform, as described below from D. H. Ballard, "Generalizing the Hough Transform to Detect Arbitrary Shapes", Pattern Recognition, Vol. 13, No. 2, pp. 111-122 (1981).
FIG. 1 is a block diagram showing the basic configuration of the conventional strict recognizing apparatus, that is, the strict recognizing apparatus based on the generalized Hough transform. In FIG. 1, the conventional recognizing apparatus comprises an object model storing unit 101 storing the shape object about one or more objects; a parameter space storing unit 102 for storing the space of a parameter describing an environment; a voting unit 103 for taking a vote in a voting space in a parameter space, for example, as a parameter space segmented in a mesh form based on a characteristic point extracted from, for example, image data, that is, one or more observed characteristic points, and an object model stored in the object model storing unit 101; and a parameter estimating unit 104 for outputting an estimated value for the parameter from a voting value obtained in the voting space.
FIG. 2 is a flowchart showing the parameter estimating method in the recognizing apparatus shown in FIG. 1. When the process starts as shown in FIG. 1, a subset in the parameter space matching the object model in each of the observed characteristic points is obtained in response to the input of the set of one or more observed characteristic points obtained by observing the environment in step S101. Then, a vote is cast for the subset. Then, in step S102, the parameter describing the environment, for example, the position of the coordinates of the center of gravity of an object, etc. is estimated from the voting value obtained in the parameter space, thereby terminating the process.
The conventional operations of the recognizing apparatus explained by referring to FIG. 2 are described further in detail. FIG. 3 shows the document containing a plurality of two-dimensional graphics. The operation of the recognizing apparatus is described below using this document as an environment to be recognized.
FIG. 4 shows an example of an object model stored in the object model storing unit 101 shown in FIG. 1. Although the object model storing unit 101 normally stores models of a plurality of objects, FIG. 4 shows one of them, that is, an object model of a heart-shaped two-dimensional figure. The object model storing unit 101 stores, as the shape information about this object model, the positions of the black dots at predetermined intervals on the outline of the heart-shape.
Assume that, using the document shown in FIG. 3, an estimated value is output with the center of gravity of the heart-shaped figure set as the parameter describing the environment. Using the image data for the document shown in FIG. 3, for example, an edge is extracted to binarize data and obtain as observed characteristic points the positions of the outline points forming part of the two-dimensional figure. FIG. 5 shows such observed characteristic points. In this example, the outline points corresponding to the heart-shaped mark and the circle-shaped mark are obtained as observed characteristic points.
Assuming that A, B, C, and D are examples of the observed characteristic points shown in FIG. 5, it is uncertain that these four points respectively correspond to which outline points of the heart-shaped mark in the document shown in FIG. 3 in the steps where these observed characteristic points are obtained. In this case, A, B, and C are outline points of the heart-shaped mark. They are shown in FIG. 5.
As described above, the position of the center of gravity of the heart-shaped mark is estimated as a parameter. Then, the position of the center of gravity corresponding to the outline points is obtained when the four observed characteristic points A, B, C, and D match the points on the outline of the object model shown in FIG. 4. When one observed characteristic point sequentially shifts on the outline of the heart-shaped mark, the locus of the center of gravity is obtained as shown in FIG. 6.
The locus of the center of gravity corresponding to one observed characteristic point indicates an inverted heart-shaped mark obtained by setting upside down the object model shown in FIG. 4. Thus, four inverted heart-shaped marks are drawn on the xy plane about the observed characteristic points A, B, C, and D.
In FIG. 6, the inverted heart-shaped mark corresponding to the outline point D of the circle-shaped mark shown in FIG. 31 does not share common intersections with the three other heart-shaped marks because the observed characteristic point D does not exist on the heart-shaped mark whose value of the center of gravity is estimated there. On the other hand, the three inverted heart-shaped marks corresponding to other observed characteristic points A, B, and C cross at one point (black dot in FIG. 6) which indicates a true center of gravity as an estimated value. To obtain the parameter estimated value, the xy plane is segmented in a mesh form. When an inverted heart-shaped mark crosses a segment of the mesh, the number of votes for the segment is incremented by 1. Thus, votes are cast for the segments of the mesh corresponding to the three inverted heart-shaped marks. When a point obtains three votes, it is output as the center of gravity, that is, the parameter estimated value, of the heart-shaped mark in the document shown in FIG. 3.
As described above, a parameter, that is, the position of the center of gravity of the heart-shaped mark in the document, on the xy plane as shown in FIG. 6 is obtained by segmenting an area, that is, a parameter space, where the center of gravity is assumed to exist is segmented in a mesh form as a voting space. An estimated value of the parameter is obtained by casting a vote for the voting space. To obtain the position of the center of gravity with precision, the area should be segmented in a fine mesh form, thereby requiring a large memory capacity to represent the voting space, that is, the parameter space.
For example, when a heart-shaped mark is written on a document page of 100 mm long and 100 mm wide and its center of gravity is to be obtained with a precision of 0.1 mm, the parameter space should be segmented in a 1,000.times.1,000 mesh form, and memory area is required for the number of segments. The larger the document, or the greater the desired precision of the position of the center of gravity, the larger is the memory capacity requirement. Under such conditions, it is difficult to successfully realize a practical recognizing apparatus.